As is known, the term “cache” generally refers to a data storage or memory device, or at least some portion of memory associated with such a device, in which data objects are typically stored for faster access. For example, in a World Wide Web or Internet-based environment, a cache may be used to temporarily store data objects previously retrieved from a Web server such that future access of this data, by the original requester or some other subsequent requesters, may be accomplished via the cache rather than via the Web server again. Such caches are typically called “cache servers” or “proxy caching servers.” However, some form of caching may also be done on one or more of the computer systems (i.e., client devices) of the requesters. Some of the well-known advantages associated with the use of a cache in such a computing environment include the realization of a savings in access and/or processing time, as well as a reduction in network traffic.
In many situations, a cache will be updated multiple times by update operations which occur in close temporal proximity to one another. A conventional technique for handling these update operations is to treat them independently. However, this technique typically suffers from poor performance. For example, the same cached object may be invalidated and recalculated multiple times resulting in significant overhead. In some cases, invalidation operations may be expensive. For example, if the cache is single threaded and lock contention is an issue, invalidation operations may add to the contention and further reduce cache throughput.
Further, if the cache is managed using data update propagation (for example, as described in J. Challenger, A. Iyengar and P. Dantzig, “A Scalable System for Consistently Caching Dynamic Web Data,” Proceedings of INFOCOM '99, the disclosure of which is incorporated by reference herein) and the update operations are to underlying data, determining cached objects affected by the changes to underlying data requires a graph traversal for each update. In another scenario, the cache may be storing sets of entities. In response to an update message, the cache then has to determine all cached sets affected by the update.
Thus, there is a need for cache management techniques which address these inefficiency and overhead issues, as well as other related issues.